class BacktrackingAlgorithm:
    @staticmethod
    def permute(nums):
        """
        全排列算法

        参数:
        nums (List[int]): 输入的列表

        返回:
        List[List[int]]: 所有全排列结果列表

        实现步骤:
        1. 创建结果列表res用于存储全排列结果。
        2. 创建辅助函数backtrack，参数为当前排列和选择列表：
            a. 如果当前排列的长度等于输入列表的长度，表示已经得到一个全排列，将其添加到结果列表res中。
            b. 遍历选择列表中的每个元素：
                i. 如果当前元素已经在排列中，跳过。
                ii. 将当前元素添加到排列中。
                iii. 递归调用backtrack，传入更新后的排列和选择列表。
                iv. 回溯完成后，将当前元素从排列中移除。
        3. 调用辅助函数backtrack，传入空的排列和输入列表。
        4. 返回结果列表res。

        """

        res = []

        def backtrack(path, choices):
            # 2a. 如果当前排列的长度等于输入列表的长度，表示已经得到一个全排列
            if len(path) == len(nums):
                res.append(path[:])
                return

            for num in choices:
                # 2b.i. 如果当前元素已经在排列中，跳过
                if num in path:
                    continue

                # 2b.ii. 将当前元素添加到排列中
                path.append(num)

                # 2b.iii. 递归调用backtrack，传入更新后的排列和选择列表
                backtrack(path, choices)

                # 2b.iv. 回溯完成后，将当前元素从排列中移除
                path.pop()

        # 3. 调用辅助函数backtrack，传入空的排列和输入列表
        backtrack([], nums)

        # 4. 返回结果列表res
        return res

    @staticmethod
    def combination_sum(candidates, target):
        """
        组合总和算法

        参数:
        candidates (List[int]): 输入的候选数字列表
        target (int): 目标和

        返回:
        List[List[int]]: 所有满足目标和的组合列表

        实现步骤:
        1. 创建结果列表res用于存储满足目标和的组合列表。
        2. 创建辅助函数backtrack，参数为当前组合、当前目标和和起始位置：
            a. 如果当前目标和等于0，表示已经得到一个满足目标和的组合，将其添加到结果列表res中。
            b. 遍历候选数字列表中的每个元素：
                i. 如果当前元素大于当前目标和，跳过。
                ii. 将当前元素添加到组合中。
                iii. 递归调用backtrack，传入更新后的组合、当前目标和减去当前元素、起始位置不变。
                iv. 回溯完成后，将当前元素从组合中移除。
        3. 调用辅助函数backtrack，传入空的组合、目标和和起始位置0。
        4. 返回结果列表res。

        """

        res = []

        def backtrack(combination, remain, start):
            # 2a. 如果当前目标和等于0，表示已经得到一个满足目标和的组合
            if remain == 0:
                res.append(combination[:])
                return

            for i in range(start, len(candidates)):
                # 2b.i. 如果当前元素大于当前目标和，跳过
                if candidates[i] > remain:
                    continue

                # 2b.ii. 将当前元素添加到组合中
                combination.append(candidates[i])

                # 2b.iii. 递归调用backtrack，传入更新后的组合、当前目标和减去当前元素、起始位置不变
                backtrack(combination, remain - candidates[i], i)

                # 2b.iv. 回溯完成后，将当前元素从组合中移除
                combination.pop()

        # 3. 调用辅助函数backtrack，传入空的组合、目标和和起始位置0
        backtrack([], target, 0)

        # 4. 返回结果列表res
        return res

    @staticmethod
    def subsets(nums):
        """
        子集算法

        参数:
        nums (List[int]): 输入的列表

        返回:
        List[List[int]]: 所有子集列表

        实现步骤:
        1. 创建结果列表res用于存储所有子集列表。
        2. 创建辅助函数backtrack，参数为当前子集、起始位置：
            a. 将当前子集添加到结果列表res中。
            b. 遍历输入列表中的每个元素，从起始位置开始：
                i. 将当前元素添加到子集中。
                ii. 递归调用backtrack，传入更新后的子集和当前位置的下一个位置。
                iii. 回溯完成后，将当前元素从子集中移除。
        3. 调用辅助函数backtrack，传入空的子集和起始位置0。
        4. 返回结果列表res。

        """

        res = []

        def backtrack(subset, start):
            # 2a. 将当前子集添加到结果列表res中
            res.append(subset[:])

            for i in range(start, len(nums)):
                # 2b.i. 将当前元素添加到子集中
                subset.append(nums[i])

                # 2b.ii. 递归调用backtrack，传入更新后的子集和当前位置的下一个位置
                backtrack(subset, i + 1)

                # 2b.iii. 回溯完成后，将当前元素从子集中移除
                subset.pop()

        # 3. 调用辅助函数backtrack，传入空的子集和起始位置0
        backtrack([], 0)

        # 4. 返回结果列表res
        return res

    @staticmethod
    def n_queens(n):
        """
        N 皇后问题算法

        参数:
        n (int): 棋盘大小

        返回:
        List[List[str]]: 所有符合条件的解法列表

        实现步骤:
        1. 创建结果列表res用于存储所有符合条件的解法列表。
        2. 创建辅助函数backtrack，参数为当前棋盘和当前行数：
            a. 如果当前行数等于棋盘大小，表示已经找到一个符合条件的解法，将其添加到结果列表res中。
            b. 遍历当前行的每个位置：
                i. 如果当前位置不满足条件（与之前的皇后冲突），跳过。
                ii. 在当前位置放置皇后。
                iii. 递归调用backtrack，传入更新后的棋盘和下一行的行数。
                iv. 回溯完成后，将当前位置的皇后移除。
        3. 创建空的棋盘board，用"."表示空位，初始化棋盘为全空。
        4. 调用辅助函数backtrack，传入初始棋盘和起始行数0。
        5. 将结果列表res中的棋盘表示转换为字符串表示。
        6. 返回结果列表res。

        """

        res = []

        def backtrack(board, row):
            # 2a. 如果当前行数等于棋盘大小，表示已经找到一个符合条件的解法
            if row == n:
                res.append(["".join(row) for row in board])
                return

            for col in range(n):
                # 2b.i. 如果当前位置不满足条件（与之前的皇后冲突），跳过
                if not is_valid(board, row, col):
                    continue

                # 2b.ii. 在当前位置放置皇后
                board[row][col] = "Q"

                # 2b.iii. 递归调用backtrack，传入更新后的棋盘和下一行的行数
                backtrack(board, row + 1)

                # 2b.iv. 回溯完成后，将当前位置的皇后移除
                board[row][col] = "."

        def is_valid(board, row, col):
            # 检查同列是否有皇后冲突
            for i in range(row):
                if board[i][col] == "Q":
                    return False

            # 检查左上方是否有皇后冲突
            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == "Q":
                    return False
                i -= 1
                j -= 1

            # 检查右上方是否有皇后冲突
            i, j = row - 1, col + 1
            while i >= 0 and j < n:
                if board[i][j] == "Q":
                    return False
                i -= 1
                j += 1

            return True

        # 3. 创建空的棋盘board，用"."表示空位，初始化棋盘为全空
        board = [["."] * n for _ in range(n)]

        # 4. 调用辅助函数backtrack，传入初始棋盘和起始行数0
        backtrack(board, 0)

        # 5. 将结果列表res中的棋盘表示转换为字符串表示
        res = [["".join(row) for row in sol] for sol in res]

        # 6. 返回结果列表res
        return res

    @staticmethod
    def solve_sudoku(board):
        """
        数独问题算法（Sudoku Problem Algorithm）

        参数：
        board (List[List[str]]): 数独棋盘的二维列表。

        返回：
        bool: 是否存在合法的解法。

        实现思路：
        1. 定义一个backtrack函数，用于递归搜索解法。
           - 遍历数独棋盘的每个位置：
             - 如果当前位置为空格，尝试填入1到9的数字：
               - 如果填入的数字满足数独规则，继续搜索下一个位置。
               - 如果填入的数字不满足数独规则，尝试下一个数字。
             - 如果当前位置为数字，直接搜索下一个位置。
           - 如果所有位置都填满且满足数独规则，说明找到一个合法解法，返回True。
           - 如果无法找到合法解法，返回False。
        2. 调用backtrack函数开始搜索。
        3. 返回是否存在合法解法。

        """

        def backtrack():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in '123456789':
                            if is_valid(i, j, num):
                                board[i][j] = num
                                if backtrack():
                                    return True
                                board[i][j] = '.'
                        return False
            return True

        def is_valid(row, col, num):
            for i in range(9):
                if board[row][i] == num:
                    return False
                if board[i][col] == num:
                    return False
                if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
                    return False
            return True

        return backtrack()


if __name__ == '__main__':
    # 示例调用全排列算法
    nums = [1, 2, 3]
    permutations = BacktrackingAlgorithm.permute(nums)
    print("全排列算法结果:")
    for permutation in permutations:
        print(permutation)
    """
    全排列算法结果:
    [1, 2, 3]
    [1, 3, 2]
    [2, 1, 3]
    [2, 3, 1]
    [3, 1, 2]
    [3, 2, 1]
    """

    # 示例调用组合总和算法
    candidates = [2, 3, 6, 7]
    target = 7
    combinations = BacktrackingAlgorithm.combination_sum(candidates, target)
    print("组合总和算法结果:")
    for combination in combinations:
        print(combination)
    """
    组合总和算法结果:
    [2, 2, 3]
    [7]
    """

    # 示例调用子集算法
    nums = [1, 2, 3]
    subsets = BacktrackingAlgorithm.subsets(nums)
    print("子集算法结果:")
    for subset in subsets:
        print(subset)
    """
    子集算法结果:
    []
    [1]
    [2]
    [3]
    [1, 2]
    [1, 3]
    [2, 3]
    [1, 2, 3]
    """

    # 示例调用N皇后问题算法
    n = 4
    n_queens_result = BacktrackingAlgorithm.n_queens(n)
    print("N皇后问题解法:")
    for i, solution in enumerate(n_queens_result):
        print(f"解法 {i+1}:")
        for row in solution:
            print(row)
        print()
    """
    N皇后问题解法:
    解法 1:
    .Q..
    ...Q
    Q...
    ..Q.

    解法 2:
    ..Q.
    Q...
    ...Q
    .Q..
    """

    # 示例调用数独问题算法
    sudoku_board = [
        ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
        ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
        ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
        ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
        ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
        ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
        ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
        ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
        ['.', '.', '.', '.', '8', '.', '.', '7', '9']
    ]
    print("数独问题是否有解：", BacktrackingAlgorithm.solve_sudoku(sudoku_board))
    for row in sudoku_board:
        print(row)

# 数独问题是否有解： True
# ['5', '3', '4', '6', '7', '8', '9', '1', '2']
# ['6', '7', '2', '1', '9', '5', '3', '4', '8']
# ['1', '9', '8', '3', '4', '2', '5', '6', '7']
# ['8', '5', '9', '7', '6', '1', '4', '2', '3']
# ['4', '2', '6', '8', '5', '3', '7', '9', '1']
# ['7', '1', '3', '9', '2', '4', '8', '5', '6']
# ['9', '6', '1', '5', '3', '7', '2', '8', '4']
# ['2', '8', '7', '4', '1', '9', '6', '3', '5']
# ['3', '4', '5', '2', '8', '6', '1', '7', '9']